package H_01simple.h_9_t_53_最大子序和;

public class Solution {
    public int maxSubArray(int[] nums) {
        // 贪心算法
        // 记录遍历时的和
        int sum = 0;
        // 记录最大值
        int res = nums[0];
        for (int i = 0; i < nums.length; i++) {

            if (sum < 0) {
                sum = nums[i];
            }else{
                sum += nums[i];
            }
            //  将之前的最大值和现在的和来比较
            res = Math.max(res, sum);
        }
        return res;
    }

    public static void main(String[] args) {
        int [] arr = {-2,1,-3,4,-1,2,1,-5,4};
        Solution solution = new Solution();
        int i = solution.maxSubArray(arr);
        System.out.println(i);
    }
}
